package leetcode

import (
	"Algorithms/util"
	"sort"
	"strconv"
	"strings"
)

//整数翻转，不能超过in32最大或者最小值，每次对10取余得一位数加到翻转后的数字上去
func Reverse(x int) int {
	var result int64
	for x != 0 {
		result = result*10 + int64(x%10)
		if result > int64(util.INT_MAX) || result < int64(util.INT_MIN) {
			return 0
		}
		x = x / 10
	}
	return int(result)
}

//给你一个整数数组 nums ，请计算数组的 中心下标 。
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
//思路：类似与计数排序的过程
func PivotIndex(nums []int) int {
	var sum = make([]int, len(nums)+1)
	sum[0] = 0
	for i := 0; i < len(nums); i++ {
		sum[i+1] = sum[i] + nums[i]
	}
	for i := 1; i < len(sum); i++ {
		if sum[i-1] == sum[len(nums)]-sum[i] {
			return i - 1
		}
	}
	return -1
}

//快速幂，迭代法，利用幂的二进制来计算，复杂度O(lgn)
//如:77=(1001101)2 -----> x^77=x^64 * x^8 * x^4 * x^1
func myPow(x float64, n int) float64 {
	var x_temp float64
	//确认幂的正负
	if n < 0 {
		x_temp = 1 / x
		n *= (-1)
	} else {
		x_temp = x
	}
	//正式开始计算
	var res float64 = 1
	for n > 0 {
		//如果二进制这里是1的话再乘，如果不是就不用管了
		if n&1 > 0 {
			res *= x_temp
		}
		x_temp *= x_temp
		n = n / 2
	}
	return res
}

//用递归法快速幂，x → x^2 → x^4 → x^9 → x^19 → x^38 → x^77
func myPowRecursion(x float64, n int) float64 {
	if n < 0 {
		return powRecursion(1/x, n*(-1))
	}
	return powRecursion(x, n)
}
func powRecursion(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	y := powRecursion(x, n/2)
	if n%2 == 1 {
		return y * y * x
	}
	return y * y
}

//你的任务是计算 ab 对 1337 取模
//a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
//利用取模分配率来计算，(a⋅b)modm=[(amodm)⋅(bmodm)]modm
var mod = 1337

//和二进制有区别的是，这回是用十进制，每次a要进行十次幂乘
func superPow(a int, b []int) int {
	res := 1
	for i := len(b) - 1; i >= 0; i-- {
		res = res * pow(a, b[i]) % mod
		a = pow(a, 10)
	}
	return res
}
func pow(x, n int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n&1 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

//1518. 换酒问题，简单递归问题
func numWaterBottles(numBottles int, numExchange int) int {
	if numExchange > numBottles {
		return numBottles
	}
	last := numBottles % numExchange
	exchange := numBottles / numExchange
	return exchange*numExchange + numWaterBottles(last+exchange, numExchange)
}

//507. 完美数
func checkPerfectNumber(num int) bool {
	temp := num
	for i := 1; i < num; i++ {
		if num%i == 0 {
			temp -= i
		}
	}
	if temp == 0 {
		return true
	}
	return false
}

//1716. 计算力扣银行的钱
func totalMoney(n int) int {
	a:=n/7
	b:=n%7
	res:=28*a+7*(a-1)*a>>1+b*a+(1+b)*b>>1
	return res
}
//1688. 比赛中的配对次数
func numberOfMatches(n int) int {
	if n<=1{
		return 0
	}
	if n%2==1{
		return n>>1+numberOfMatches(n>>1+1)
	}
	return n>>1+numberOfMatches(n>>1)
}

//306. 累加数
func isAdditiveNumber(num string) bool {
	n := len(num)
	if n < 3 {
		return false
	}
	first := 0
	for i := 0; i < n; i++ {
		if num[0] == '0' && i > 0 {
			continue
		}
		first = first*10 + int(num[i]-'0')
		second := 0
		for j := i + 1; j < n; j++ {
			if num[i+1] == '0' && j > i+1 {
				continue
			}
			second = second*10 + int(num[j]-'0')
			third := 0
			for k := j + 1; k < n; k++ {
				if num[j+1] == '0' && k > j+1 {
					continue
				}
				third = third*10 + int(num[k]-'0')
				if first+second == third {
					if k+1 == n {
						return true
					}
					if isAdditiveNumber(num[i+1:]) {
						return true
					}
				}
			}
		}
	}
	return false
}

//67. 二进制求和
func addBinary(a string, b string) string {
	if len(a) == 0 {
		return b
	}
	if len(b) == 0 {
		return a
	}
	var c byte = 0 //进位
	var res = ""
	i, j := len(a)-1, len(b)-1
	for i >= 0 || j >= 0 {
		if i >= 0 {
			c += a[i] - '0'
			i--
		}
		if j >= 0 {
			c += b[j] - '0'
			j--
		}
		res = string(c%2+'0') + res
		c >>= 1
	}
	if c > 0 {
		res = string(c+'0') + res
	}
	return res
}

var q = []string{"1"}

//38. 外观数列
func countAndSay(n int) string {
	if n <= len(q) {
		return q[n-1]
	}
	for i := len(q) - 1; i < n-1; i++ {
		last := q[len(q)-1]
		index := 0
		res := ""
		for index < len(last) {
			tmp := last[index]
			sum := int64(1)
			for index+1 < len(last) {
				if last[index+1] == tmp {
					index++
					sum++
				} else {
					break
				}
			}
			res += strconv.FormatInt(sum, 10) + string(tmp)
			index++
		}
		q = append(q, res)
	}
	return q[n-1]
}

//539. 最小时间差
func findMinDifference(timePoints []string) int {
	timeNum := make([]int, len(timePoints))
	for i := range timePoints {
		ss := strings.Split(timePoints[i], ":")
		honor, _ := strconv.ParseInt(ss[0], 10, 32)
		minute, _ := strconv.ParseInt(ss[1], 10, 32)
		time := int(honor)*60 + int(minute)
		timeNum[i] = time
	}
	sort.Ints(timeNum)
	diff := 24*60 - timeNum[len(timeNum)-1] + timeNum[0]
	for i := 1; i < len(timeNum); i++ {
		if timeNum[i]-timeNum[i-1] < diff {
			diff = timeNum[i] - timeNum[i-1]
		}
	}
	return diff
}

//2006. 差的绝对值为 K 的数对数目
func countKDifference(nums []int, k int) int {
	ans := 0
	for i := range nums {
		temp := nums[i]
		for j := i + 1; j < len(nums); j++ {
			if temp-nums[j] == k || nums[j]-temp == k {
				ans++
			}
		}
	}
	return ans
}

//1447. 最简分数，辗转相除法求最大公约数
func simplifiedFractions(n int) []string {
	gcd := func(a, b int) int {
		//以除数和余数反复做除法运算，当余数为 0 时，
		//取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
		for a != 0 {
			a, b = b%a, a
		}
		return b
	}
	ans := make([]string, 0)
	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			if gcd(i,j)==1{
				temp:=strconv.FormatInt(int64(j),10)+"/"+strconv.FormatInt(int64(i),10)
				ans=append(ans, temp)

			}
		}
	}
	return ans
}
//136. 只出现一次的数字，巧用异或
func singleNumber(nums []int) int {
	ans:=0
	for i:=range nums{
		ans^=nums[i]
	}
	return ans
}
//338. 比特位计数
func countBits(n int) []int {
	res:=make([]int,n+1)
	for i:=range res{
		res[i]=countBit(i)
	}
	return res
}
func countBit(n int)int{
	count:=0
	for n>0{
		n=n&(n-1)
		count++
	}
	return count
}

//399. 除法求值
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	type pair struct {
		num float64
		val string
	}
	m := make(map[string][]pair)
	for i := range equations {
		first := equations[i][0]
		second := equations[i][1]
		if _, ok := m[first]; !ok {
			m[first] = []pair{}
		}
		if _, ok := m[second]; !ok {
			m[second] = []pair{}
		}
		m[first] = append(m[first], pair{
			num: values[i],
			val: second,
		})
		m[second] = append(m[second], pair{
			num: 1 / values[i],
			val: first,
		})
	}
	var dfs func(pair, string, map[string]bool) float64
	dfs = func(p pair, s string, visited map[string]bool) float64 {
		if visited[p.val] {
			return -1
		}
		if p.val == s {
			return p.num
		}
		visited[p.val] = true
		for i := range m[p.val] {
			tmp := dfs(m[p.val][i], s, visited)
			if tmp != -1 {
				return tmp * p.num
			}
		}
		return -1
	}
	res := make([]float64, len(queries))
	for i := range queries {
		first := queries[i][0]
		second := queries[i][1]
		tmp := -1.0
		visited := make(map[string]bool)
		visited[first] = true
		if _, ok := m[first]; !ok {
			res[i] = -1.0
			continue
		}
		if first == second {
			res[i] = 1.0
			continue
		}
		for i := range m[first] {
			tmp = dfs(m[first][i], second, visited)
			if tmp != -1 {
				break
			}
		}
		res[i] = tmp
	}
	return res
}
//279. 完全平方数 贪心算法
func numSquares(n int) int {
	arr:=make([]int,0)
	for i:=1;i*i<=n;i++{
		arr=append(arr, i*i)
	}
	dp:=make([]int,n+1)
	for i:=0;i<len(arr);i++{
		dp[arr[i]]=1
	}
	for i:=range dp{
		if dp[i]!=0{
			for j:=range arr{
				if i+arr[j]>n{
					break
				}
				if dp[i+arr[j]]==0{
					dp[i+arr[j]]=dp[i]+1
				}else {
					dp[i+arr[j]]=min(dp[i+arr[j]],dp[i]+1)
				}
			}
		}
	}
	return dp[n]
}
//461. 汉明距离
func hammingDistance(x int, y int) int {
	temp:=x^y
	ans:=0
	for temp>0{
		if temp&1==1{
			ans++
		}
		temp=temp>>1
	}
	return ans
}